const MAX = Infinity;
let graph = [
  [0, 34, 46, MAX, MAX, 19],
  [34, 0, MAX, MAX, 12, MAX],
  [46, MAX, 0, 17, MAX, 25],
  [MAX, MAX, 17, 0, 38, 25],
  [MAX, 12, MAX, 38, 0, 26],
  [19, MAX, 25, 25, 26, 0]
];

// 初始化 shortEdge 数组
// 理解 i 终点
// adjVex 起点
// lowcost 0 已加入到U集合 
function initShortEdge(graph, startV) {
    let shortEdge = [];
    let vNums = graph.length;
    for(let i = 0; i < vNums; i++) {
        shortEdge.push({
            adjVex: startV,            
            lowcost: graph[startV][i]
        })
    }
    shortEdge[startV].lowcost = 0;
    return shortEdge;
}

// let shortEdge = initShortEdge(graph, 0);

function minEdge(shortEdge) {
    let min = MAX;
    let k;
    shortEdge.forEach((e, index) => {
        // 注意 U 集中的元素，即shortEdge.lowcost = 0 的元素不再进行比较
        if(e.lowcost != 0 && e.lowcost < min) {
            min = e.lowcost;
            k = index;
        }
    });
    return k; // 返回邻接点
}
// console.log(shortEdge);
// console.log(minEdge(shortEdge));

// 输出生成树的某条边的起点，终点和权值
function output(k, shortEdge) {
    console.log(shortEdge[k].adjVex + ' -> ' + k + '  weight: ' + shortEdge[k].lowcost);
}

function prim(g, startV) {
    let nums = g.length;
    let shortEdge = initShortEdge(g, startV);
    for(let i = 0; i < nums - 1; i++) {
        let k = minEdge(shortEdge);
        output(k, shortEdge); // 输出生成树中的路径
        shortEdge[k].lowcost = 0; // 加入U集合
        // 更新shortEdge
        for(let j = 0; j < nums; j++) {
            if(graph[k][j] < shortEdge[j].lowcost) {
                shortEdge[j].lowcost = graph[k][j];
                shortEdge[j].adjVex = k;
            }
        }      
    }
}

prim(graph, 0);
/**
0 -> 5  weight: 19
5 -> 2  weight: 25
2 -> 3  weight: 17
5 -> 4  weight: 26
4 -> 1  weight: 12
 */